#include<iostream>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<chrono>
using namespace std;
/// Time the sort by chrono.
int insertion (vector<double>&_arr);
int main (int argc,char *argv[])
{
/// The unit seems be one nano second.
    typedef chrono::high_resolution_clock myclock;
    int n=-1;
    cin >> n;
    vector<double> arr(n);
    for (vector<double>::iterator arr_iterator=arr.begin();
	 arr_iterator!=arr.end();
	 ++arr_iterator)
	cin >> *arr_iterator;
/// Start the timer.
    myclock::time_point beginning=myclock::now();
    insertion(arr);
/// Finish the timer.
    myclock::duration d=myclock::now()-beginning;
    cout << "A: ";
    for (vector<double>::iterator arr_iterator=arr.begin();
	 arr_iterator !=arr.end();
	 ++arr_iterator)
	cout<<*arr_iterator<<" ";
    cout<<endl;
    cout<<"time: "<<d.count() <<endl;
    return 0;
};

int insertion(vector<double>&_arr)
{
    for (int j=1;j<_arr.size();j++){
	double key=_arr[j];
// Insert A[j] into the sorted sequence A[1...j-1].                        
	int i=j-1;
	while (i>=0&&_arr[i]>key){
	    _arr[i+1]=_arr[i];
	    i=i-1;
	}
	_arr[i+1]=key;
    }
    return 0;
};
